package com.fjl.list.leetcode206;

import com.fjl.list.ListNode;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/21 9:48
 */
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
public class ReverseListClass {

    public ListNode reverseList(ListNode head) {
        // 空链表或者单个节点的链表直接原样return
        if (head == null || head.next == null) return head;

        // 由于单链表的结构，至少要用三个指针才能完成迭代反转
        // cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head.next;
        while (cur != null) {
            // 逐个结点反转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
            if (nxt != null) {
                nxt = nxt.next;
            }
        }
        return pre;
    }

    // 递归
    //值得一提的是，递归操作链表并不高效。
    //递归解法和迭代解法相比，时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。
    //所以递归操作链表可以用来练习递归思维，但是考虑效率的话还是使用迭代算法更好。
    public ListNode reverseList1(ListNode head) {
        // 空链表或者单个节点的链表直接原样return
        if (head == null || head.next == null) return head;
        ListNode last = reverseList1(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}
